package com.leetcode.No1687;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 从仓库到码头运输箱子
 * @author: Wang Zhihua
 * @date: 2022-12-08
 */
public class Solution {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int result = getResult(boxes, maxBoxes, maxWeight);

        int len = boxes.length;
        int[] tmpBox;
        for (int i = 0; i < len / 2; ++i) {
            tmpBox = boxes[i];
            boxes[i] = boxes[len - 1 - i];
            boxes[len - 1 - i] = tmpBox;
        }

        return Math.min(result, getResult(boxes, maxBoxes, maxWeight));
    }

    private int getResult(int[][] boxes, int maxBoxes, int maxWeight) {
        int len = boxes.length;
        int[] start = new int[len];
        int[] routeNum = new int[len];

        int idx = 0;
        int tmpBoxNum = 0;
        int tmpWight = 0;
        for (int i = 0; i < len; ++i) {
            ++tmpBoxNum;
            tmpWight += boxes[i][1];
            while (tmpBoxNum > maxBoxes || tmpWight > maxWeight) {
                --tmpBoxNum;
                tmpWight -= boxes[idx][1];
                ++idx;
                routeNum[i] -= (boxes[idx][0] == boxes[idx - 1][0]) ? 0 : 1;
            }
            start[i] = idx;
            if (i == 0) {
                routeNum[0] = 2;
            } else {
                routeNum[i] += routeNum[i - 1] + ((boxes[i][0] == boxes[i - 1][0]) ? 0 : 1);
            }
        }

        int result = 0;
        int end = len - 1;
        while (end >= 0) {
            result += routeNum[end];
            end = start[end] - 1;
        }
        return result;
    }

    @Test
    public void test01() {
        int[][] boxes;
        int portsCount;
        int maxBoxes;
        int maxWeight;

        boxes = new int[][]{{1,1}, {2,1}, {1,1}};
        portsCount = 2;
        maxBoxes = 3;
        maxWeight = 3;
        System.out.println(boxDelivering(boxes, portsCount, maxBoxes, maxWeight));

        boxes = new int[][]{{1,2}, {3,3}, {3,1}, {3,1}, {2,4}};
        portsCount = 3;
        maxBoxes = 3;
        maxWeight = 6;
        System.out.println(boxDelivering(boxes, portsCount, maxBoxes, maxWeight));

        boxes = new int[][]{{1,4}, {1,2}, {2,1}, {2,1}, {3,2}, {3,4}};
        portsCount = 3;
        maxBoxes = 6;
        maxWeight = 7;
        System.out.println(boxDelivering(boxes, portsCount, maxBoxes, maxWeight));

        boxes = new int[][]{{2,4}, {2,5}, {3,1}, {3,2}, {3,7}, {3,1}, {4,4}, {1,3}, {5,2}};
        portsCount = 5;
        maxBoxes = 5;
        maxWeight = 7;
        System.out.println(boxDelivering(boxes, portsCount, maxBoxes, maxWeight));

        boxes = new int[][]{{61,4840},{66,16490},{54,15479},{48,5555},{25,3120},{47,1010},{30,3236},{7,9270},{55,14900},{48,11603},{104,12299},{3,8266},{3,1440},{15,5659},{72,13285},{32,10642},{26,5780},{88,15220},{16,3808},{27,11203},{41,7645},{79,10232},{73,403},{86,11181},{25,5789},{12,15415},{59,2075},{60,11185},{39,2213},{103,12049},{99,9585},{40,16489},{71,3282},{47,10552},{10,11910},{86,7606},{6,654},{30,14945},{14,3796},{22,5430},{10,13458},{74,2169},{81,10010},{92,6330},{104,778},{100,3311},{98,5975},{56,15520},{13,11700},{19,6890},{99,2910},{62,1393},{48,5638},{9,10967},{38,945},{23,14549},{43,4081},{42,4540},{82,5832},{69,5072},{19,15047},{85,4330},{57,3549},{32,6955},{46,15456},{80,1358},{58,25},{95,9401},{10,15268},{32,12504},{10,4724},{83,4816},{45,2084},{33,7725},{32,3637},{103,7506},{103,51},{69,6945},{42,4017},{66,5596},{83,305},{56,10441},{70,3892},{78,2290},{50,6269},{23,14932},{17,11895},{43,3679},{39,3086},{43,16224},{12,13993},{92,14876},{6,1219},{65,8544},{25,658},{79,5722},{19,14103},{80,16496},{56,8778},{44,4481},{36,14814},{77,2370},{2,7206},{100,1700},{24,1636},{36,8805},{46,7068},{7,13167},{45,8375},{63,9633},{83,8546},{13,15183},{73,14140},{12,1395},{101,2581},{2,5718},{16,2783},{34,9200},{42,10048},{74,1353},{74,2485},{33,4091},{21,9159},{79,10195},{1,9576},{63,11647},{104,5794},{103,2786},{46,121},{23,5173},{35,7066},{13,12041},{51,9573},{56,2992},{81,4133},{58,9161},{27,9496},{86,4972},{33,11241},{88,11329},{69,3844},{47,1487},{94,15931},{48,11569},{15,2003},{26,11104},{33,6961},{6,15453},{2,11193},{14,3942},{94,10791},{71,1871},{98,13280},{73,8641},{21,9413},{22,12239},{38,14552},{92,14876},{43,4579},{21,12583},{67,13959},{71,9938}};
        portsCount = 106;
        maxBoxes = 74;
        maxWeight = 16517;
        System.out.println(boxDelivering(boxes, portsCount, maxBoxes, maxWeight));
    }
}
